package com.yww.algorithm.sort;

import java.util.Arrays;

/**
 * @author yww
 * @description 单边快速排序，Lomuto方案
 * @since 2024/2/24 15:42
 */
public class QuickSortLomuto {
    public static void sort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }

    private static void quick(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(arr, left, right); // 分区
        quick(arr, left, p - 1); // 左递归
        quick(arr, p + 1, right); // 右递归
    }

    private static int partition(int[] arr, int left, int right) {
        int pv = arr[right]; // 选取最右边的值为基准值
        int i = left; // i找比pv大的元素
        int j = left; // j找比pv小的元素

        while (j < right) { // 开始寻找
            if (arr[j] < pv) { // j找到了比pv小的元素
                if (i != j) {
                    swap(arr, i, j);
                }
                i++;
            }
            j++; // j每次都前进，i找>=pv的值就停下
        }
        swap(arr, i, right); // 现在i就是分区索引，交换基准值
        return i;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void main(String[] args) {
        int[] a = {6, 5, 4, 3, 2, 1};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
